# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

    def __str__(self):
        return str({
            'id': id(self),
            'val': self.val,
            'isLeaf': self.isLeaf,
            'topLeft': str(self.topLeft),
            'topRight': str(self.topRight),
            'bottomLeft': str(self.bottomLeft),
            'bottomRight': str(self.bottomRight),
        })


class Solution:
    def construct(self, grid: list) -> Node:
        n = len(grid)
        mid = n // 2
        if n == 1:
            node = Node(grid[0][0], True, None, None, None, None)
        else:
            tl = self.construct([i[:mid] for i in grid[:mid]])
            tr = self.construct([i[mid:] for i in grid[:mid]])
            bl = self.construct([i[:mid] for i in grid[mid:]])
            br = self.construct([i[mid:] for i in grid[mid:]])
            if tl.isLeaf and tl.val == tr.val and tl.val == bl.val and tl.val == br.val:
                node = Node(tl.val, True, None, None, None, None)
            else:
                node = Node('*', False, tl, tr, bl, br)
        return node


data = [[1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1],
        [1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 0, 0, 0, 0]]
a = Solution().construct(data)
print(a)
